package LRUWithLinkedList

import "fmt"

type ListNode struct {
	Key   int
	Value int
	Next  *ListNode
}
type LRU struct {
	capacity int
	size     int
	list     *ListNode
}

type LRUer interface {
	init(capacity_ int)
	Get(key int) bool
	Put(key, value int)
	update(key int)
	find(key int) *ListNode
}

func (e *LRU) init(capacity_ int) {
	e.capacity = capacity_
}

func (e *LRU) Get(key int) bool {
	result := e.find(key)
	if result == nil {
		return false
	}

	e.update(result)
	return true
}

func (e *LRU) Put(key, value int) {
	result := e.find(key)

	if result != nil {
		e.update(result)
		e.list.Value = value
		return
	}

	if e.size < e.capacity {
		var head *ListNode = new(ListNode)

		head.Value = value
		head.Key = key
		head.Next = e.list

		e.list = head
		e.size++
		return
	}

	var getTailNode = func() *ListNode {
		var pre = e.list

		for pre.Next != nil {
			pre = pre.Next
		}
		return pre
	}

	tailNode := getTailNode()

	e.update(tailNode)

	e.list.Value = value
	e.list.Key = key
}
func (e *LRU) update(node *ListNode) {

	var getFrontNode = func() *ListNode {
		var back *ListNode = nil
		pre := e.list

		for pre != nil {
			if pre.Key == node.Key {
				return back
			}

			back = pre
			pre = pre.Next
		}
		return back
	}

	front := getFrontNode()

	if front == nil {
		return
	}

	front.Next = node.Next
	node.Next = e.list
	e.list = node
}

func (e *LRU) find(key int) *ListNode {
	if e.list == nil {
		return nil
	}

	pre := e.list
	for pre != nil {
		if pre.Key == key {
			return pre
		}
		pre = pre.Next
	}
	return nil
}

func main() {
	lru := new(LRU)
	lru.init(1)

	for i := 0; i < 5; i++ {
		lru.Put(i, i+7)
	}

	for i := 0; i < 5; i++ {
		if lru.Get(i) {
			fmt.Println("success")
		} else {
			fmt.Println("no exixt")
		}
	}
}
